H1P3

题目

设 $A = {1, 2, \dots, n}$ 与正整数 $k$ 。求从 $A$ 中选择如下 $(\binom{k + 1}{2})$ 个子集的方案数：

\begin{array}{cccccc} S_{1, 1} \\ S_{2, 1} & S_{2, 2} \\ ⋮ & ⋮ & ⋱ \\ S_{k, 1} & S_{k, 2} & \dots & S_{k, k} \end{array}

满足约束：

S_{i, j} \subseteq S_{i - 1, j} (i > 1), S_{i, j} \subseteq S_{i, j - 1} (j > 1) .

解答

2^{k n}

考虑以集合为节点，包含关系为边的有向图 $G (V, E)$ ：如果存在从 $A$ 到 $B$ 的边，那么有约束关系 $B \subseteq A$ ，这构成了一个约束系统

可以通过特征向量形式化这一点：

χ (x) := (1_{x \in A_{1}}, \dots, 1_{x \in A_{n}}) \in {0, 1}^{n}

A_{i} \subseteq A_{j} ⟹ 1_{x \in A_{i}} \leq 1_{x \in A_{j}}

给定全集 $U$ ，通过特征向量可以定义细分区域：

R_{σ} = {x \in U : χ (x) = σ}, σ \in {0, 1}^{n} 且满足所有约束

此题的核心就是求解给定图上的细分区域个数，也就是满足约束的 $σ$ 的个数

如果图为 $A \to B \to C$ ，那么细分区域有 $∁ A, A - B, B - C, C$ ，共 $4$ 个。一般地，如果此图是一条 $n$ 元单向链，那么细分区域有 $n + 1$ 个

现在，考虑这个图：

A \to B \to D, A \to C \to D

用文氏图可以看出，细分区域有 $∁ A, A - (B \cup C), B - C, C - B, (B \cap C) - D, D$ ，共 $6$ 个
由于我们只关注图上的细分区域个数，可以认为该图和下面的图等价：

A \to M \to F \to N \to D

这种变换非常无聊，真正有价值的是对子图的变换。如果 $A \to B \to D, A \to C \to D$ 只是一个子图，而 $B$ 除此之外还连着其他边，那么变换为 $A \to M \to F \to N \to D$ 显然是不合法的操作。下面这个变换结果更有用，它在 $B$ 连着其他边的情况下仍然合法，只在 $C$ 连着其他边时不合法：

A \to M \to B \to N \to D

考虑这个变换的实际意义， $M$ 是对 $B \cup C$ 的重命名， $N$ 是对 $B \cap C$ 的重命名，依此可以定义原图 $G$ 的特征向量 $σ$ 与新图 $G^{'}$ 的特征向量 $σ^{'}$ 间的保持 “是否满足约束” 性质的双射，从而证明此变换不改变图的细分区域个数，是等价变换。

然后，考虑对如下子图的变换：

A \to B \to D, A \to C_{1} \to C_{2} \to \dots \to C_{n} \to D

依旧文氏图，可以发现，只需要 $C_{1}, C_{2} \dots C_{n}$ 没有其他边，就可以等价变换为一条头为 $A$ ，尾为 $D$ ，中间有 $2 n + 1$ 个节点的链，正中间的节点是 $B$ ，剩余节点均被重命名

上面这个变换已经足够处理本题的约束图，反复运用变换可以将图变为一条 $2^{k} - 1$ 个节点的链，故有 $2^{k}$ 个细分区域

对于 $A$ 中的每一个元素，可以自由选择其位于的细分区域，以此重建图中的集合，由乘法原理，答案为 $2^{k n}$